package com.smday.linkedlist;

/**
 * @author Summerday
 */
public class DoubleLinkedListDemo {

    public static void main(String[] args) {
        DoubleLinkedList dl = new DoubleLinkedList();

        Node n1 = new Node(4);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(1);
        Node n5 = new Node(5);
        dl.addByOrder(n1);
        dl.addByOrder(n2);
        dl.addByOrder(n3);
        dl.addByOrder(n4);
        dl.addByOrder(n5);
        dl.show();
    }
}

//双向链表
class DoubleLinkedList {

    //虚拟头节点
    private Node dummyNode;

    public DoubleLinkedList() {
        this.dummyNode = new Node(0);
    }

    public Node getDummyNode() {
        return dummyNode;
    }

    /**
     * 遍历打印
     */
    public void show() {

        if (dummyNode.next == null) {
            System.out.println("链表为空!");
            return;
        }
        Node node = dummyNode.next;
        while (node != null) {
            System.out.println(node);
            node = node.next;
        }
    }

    //添加到链表的最后位置
    public void add(Node newNode) {
        Node node = dummyNode;
        //找到最后一个节点
        while (node.next != null) {
            node = node.next;
        }
        //此时node为最后一个节点
        node.next = newNode;
        newNode.prev = node;
    }

    public void addByOrder(Node newNode){

        Node node = dummyNode;

        ////如果是空,直接插入
        if(node.next == null){
            dummyNode.next = newNode;
            //下面这句区别在于第一个节点prev是否指向dummy
            newNode.prev = dummyNode;
            return;
        }
        //遍历找到第一个比newNode.data大的Node node
        while(node.next!=null&&node.next.data<newNode.data){
            node = node.next;
        }
        //退出循环的其中一种情况
        if(node.next == null){
            node.next = newNode;
        }else {
            //在中间找到目标位置,此时node.data<newNode.data<node.next.data
            Node next = node.next;
            node.next = newNode;
            newNode.prev = node;
            newNode.next = next;
            next.prev = newNode;
        }

    }

    //修改一个节点的内容
    public void update(int oldData, int newData) {
        //寻找要修改节点的内容
        Node node = getNode(oldData);
        //说明是找到了
        if(node == null){
            System.out.println("未找到");
        }else {
            node.data = newData;
        }
    }

    //删除所有data节点
    public void delete(int data){
        //寻找data = oldData的节点(节点为空或者数据相等时退出循环)
        Node node;
        while ((node = getNode(data))!=null){
            node.prev.next = node.next;
            if(node.next != null){
                node.next.prev = node.prev;
            }
            node.prev = null;
            node.next = null;
        }
        System.out.println("未找到");
    }

    //删除第一个data节点
    public void deleteOne(int data){
        //寻找data = oldData的节点(节点为空或者数据相等时退出循环)
        Node node;
        if ((node = getNode(data))!=null){
            node.prev.next = node.next;
            //如果node为最后一个节点,下面这句将会空指针
            if(node.next != null){
                node.next.prev = node.prev;
            }
            node.prev = null;
            node.next = null;
        }else {
            System.out.println("未找到");
        }
    }
    /**
     * 找到对应的节点并返回,如果没找到则返回null
     * @param data
     * @return
     */
    private Node getNode(int data){

        Node node = dummyNode.next;
        //寻找data = oldData的节点(节点为空或者数据相等时退出循环)
        while (node != null && node.data != data) {
            node = node.next;
        }
        return node;
    }

}
class Node {
    int data;
    Node prev;
    Node next;
    public Node(int data) {
        this.data = data;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}